package com.mashibing.class14;

import java.util.PriorityQueue;

/**
 * 贪心算法的解题套路实战
 * 一块金条切成两半，是需要花费和长度数值一样的铜板的。
 * 比如长度为20的金条，不管怎么切，都要花费20个铜板。 一群人想整分整块金条，怎么分最省铜板?
 *
 * 例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为60，金条要分成10，20，30三个部分。
 *
 * 如果先把长度60的金条分成10和50，花费60; 再把长度50的金条分成20和30，花费50;一共花费110铜板。
 * 但如果先把长度60的金条分成30和30，花费60;再把长度30金条分成10和20， 花费30;一共花费90铜板。
 * 输入一个数组，返回分割的最小代价。
 */
public class Code02_LessMoneySplitGold {
    // 纯暴力！
    public static int lessMoney1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        // 初始化的时候 pre的代价是 0
        return process(arr, 0);
    }

    // 等待合并的数都在arr里，pre之前的合并行为产生了多少总代价
    // arr中只剩一个数字的时候，停止合并，返回最小的总代价
    public static int process(int[] arr, int pre) {
        if (arr.length == 1) {
            return pre;
        }
        int ans = Integer.MAX_VALUE;
        // arr 0 1 2 3 4 5 6
        // 0 1
        // 0 2
        // 0 3
        // 0 4
        // 0 5
        // 0 6
        // 1 2
        // 1 3
        // ....
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                ans = Math.min(ans, process(copyAndMergeTwo(arr, i, j), pre + arr[i] + arr[j]));
            }
        }
        return ans;
    }

    // 合并 arr中的第i号元素 和 第j号元素 生成一个新的数组 返回.
    // 生成的新数组中 arr数组中的第i号元素 和 第j号元素会被删除, arr[i] 和 arr[j] 相加的值会作为新值插入新数组的末尾.
    // [3 2 4 7]
    // [0] 和 [1] 合并 则 3 + 2 = 5 --> [5 4 7]
    // [0] 和 [3] 合并 则 3 + 4 = 7 --> [2 7 7]
    public static int[] copyAndMergeTwo(int[] arr, int i, int j) {
        int[] ans = new int[arr.length - 1];
        int ansi = 0;
        for (int arri = 0; arri < arr.length; arri++) {
            if (arri != i && arri != j) {
                ans[ansi++] = arr[arri];
            }
        }
        ans[ansi] = arr[i] + arr[j];
        return ans;
    }

    public static int lessMoney2(int[] arr) {
        // 准备一个小根堆(优先级队列).
        PriorityQueue<Integer> pQ = new PriorityQueue<Integer>();
        // 将arr中所有数据放入小根堆中.
        for (int i = 0; i < arr.length; i++) {
            pQ.add(arr[i]);
        }
        int sum = 0;
        int cur = 0;
        while (pQ.size() > 1) {// 只要小根堆中数据大于一个
            cur = pQ.poll() + pQ.poll(); // 弹出连个数据 相加 赋值给cur
            sum += cur; // cur累加到sum中
            pQ.add(cur); // 当前的cur插入优先级队列中.
        }
        return sum;
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * (maxValue + 1));
        }
        return arr;
    }

    public static void main(String[] args) {
        int testTime = 100000;
        int maxSize = 6;
        int maxValue = 1000;
        for (int i = 0; i < testTime; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);
            if (lessMoney1(arr) != lessMoney2(arr)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }

}
